﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Inspired.Euler
{
    /// <summary>
    /// If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.
    /// 
    /// Not all numbers produce palindromes so quickly. For example,
    /// 
    /// 349 + 943 = 1292,
    /// 1292 + 2921 = 4213
    /// 4213 + 3124 = 7337
    /// 
    /// That is, 349 took three iterations to arrive at a palindrome.
    /// 
    /// Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome.
    /// A number that never forms a palindrome through the reverse and add process is called a Lychrel number.
    /// Due to the theoretical nature of these numbers, and for the purpose of this problem,
    /// we shall assume that a number is Lychrel until proven otherwise.
    /// 
    /// In addition you are given that for every number below ten-thousand, it will either
    ///     (i) become a palindrome in less than fifty iterations, or,
    ///     (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome.
    /// 
    /// In fact, 10677 is the first number to be shown to require over fifty iterations before
    /// producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).
    /// 
    /// Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.
    /// 
    /// How many Lychrel numbers are there below ten-thousand?
    /// </summary>
    public static class Problem055
    {
        /// <summary>
        /// How many Lychrel numbers are there below ten-thousand?
        /// </summary>
        [EulerProblem(55, Title = "How many Lychrel numbers are there below ten-thousand?")]
        public static long Solve()
        {
            int count = 0;
            for (long number = 1; number < 10000; number++)
            {
                count = count + (number.IsLychrel() ? 1 : 0);

                //count = count + (
                //    !number.AsEnumerable().Permute()
                //        .Where(seq => !seq.Contains(0))
                //        .Select(seq => seq.ToInt64())
                //        .Where((candidate, index) => index >= 50 || ((int)(number + number.Reverse())).IsPalindrome(10))
                //        .Any() ? 1 : 0);
            }
            return count;
        }

        static bool IsLychrel(this long number)
        {
            BigInteger result = number;
            int tries = 0;
            do
            {
                result = BigInteger.Add(result, result.Reverse());
            }
            while (++tries < 50 && !result.IsPalindrome());
            return tries >= 50;
        }
    }
}
